package com.lhcai.nk.medium;

/**
 * @author lhcstart
 * @create 2023-02-18 21:50
 */

import javax.sound.midi.Soundbank;
import java.nio.IntBuffer;
import java.nio.MappedByteBuffer;
import java.util.Scanner;

/**
 * 描述
 * 查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
 * 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！
 * 数据范围：字符串长度 1≤length≤300
 * 进阶：时间复杂度：O(n^3) ，空间复杂度：O(n)
 * 输入描述：
 * 输入两个字符串
 * <p>
 * 输出描述：
 * 返回重复出现的字符
 */
public class HJ65 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s1 = sc.next();
            String s2 = sc.next();

//            System.out.println(solution2(s1, s2));
            System.out.println(solution(s1, s2));
        }
    }


    public static String solution(String s1, String s2) {
        //判定子串的长短
        String shortStr = s1.length() > s2.length() ? s2 : s1;
        int m = shortStr.length();
        String longStr = s1.length() > s2.length() ? s1 : s2;
        int n = longStr.length();

        int[][] dp = new int[m + 1][n + 1];
        int maxlen = 0;
        int index = 0;

        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (shortStr.charAt(i - 1) == longStr.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                    if (dp[i][j] > maxlen) {
                        maxlen = dp[i][j];
                        index = i;//i为结尾字符
                    }
                }
            }
        }
        return shortStr.substring(index - maxlen, index);
    }


    //********双重for循环，遍历短字符串的所有子串，判断是否被长串包含，获取最大长度
    public static String solution2(String s1, String s2) {
        //判定子串的长短
        String shortStr = s1.length() > s2.length() ? s2 : s1;
        String longStr = s1.length() > s2.length() ? s1 : s2;

        if (longStr.contains(shortStr)) {
            return shortStr;
        }
        String res = "";
        int len = 0;
        int index = 0;
        for (int i = 0; i < shortStr.length(); i++) {
            // 剪枝，子串长度已经不可能超过maxLen，退出循环
            if (shortStr.length() - i + 1 <= len) {
                break;
            }

            for (int j = shortStr.length(); j > i; j--) {
                String str = shortStr.substring(i, j);
                if (longStr.contains(str) && len < str.length()) {
                    len = str.length();
                    index = i;
                }
            }
        }
        return shortStr.substring(index, index + len);
    }
}

